package structure;

public class MyLinkedList1 {
    private static class Node {
        int val;
        Node next;

        Node(int val) {
            this.val = val;
        }
    }

    // 头节点
    public Node head;

    // 头插法
    public void addFirst(int val) {
        Node node = new Node(val);
        node.next = head;
        head = node;
    }

    // 尾插法
    public void addLast(int val) {
        if (head == null) {
            head = new Node(val);
            return;
        }
        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = new Node(val);
    }

    // 插入指定位置
    public void addIndex(int val, int index) {
        if (index == 0) {
            addFirst(val);
            return;
        }
        if (index == size()) {
            addLast(val);
            return;
        }
        if (index < 0 || index > size()) {
            return;
        }

        Node indexPrev = findIndexPrev(index);
        Node node = new Node(val);
        node.next = indexPrev.next;
        indexPrev.next = node;
    }

    private Node findIndexPrev(int index) {
        Node cur = head;
        while (index - 1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

    // 链表长度
    public int size() {
        Node cur = head;
        int size = 0;
        while (cur != null) {
            size++;
            cur = cur.next;
        }
        return size;
    }

    public boolean contains(int val) {
        Node cur = head;
        while (cur != null) {
            if (cur.val == val) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    public void remove(int val) {
        if (head.val == val) {
            head = head.next;
        }
        Node prev = head;
        Node removeNode = prev.next;
        while (removeNode != null) {
            if (removeNode.val == val) {
                prev.next = removeNode.next;
                return;
            }
            prev = removeNode;
            removeNode = removeNode.next;
        }
    }

    public void removeAll(int val) {
        Node prev = head;
        Node removeNode = prev.next;
        while (removeNode != null) {
            if (removeNode.val == val) {
                prev.next = removeNode.next;
            }else {
                prev = removeNode;
            }
            removeNode = removeNode.next;
        }

        if (head.val == val) {
            head = head.next;
        }
    }

    public void print() {
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        MyLinkedList1 linkedList1 = new MyLinkedList1();
        linkedList1.addFirst(2);
        linkedList1.addFirst(3);
        linkedList1.addFirst(2);
        linkedList1.addFirst(5);
        linkedList1.addIndex(5,2);
        linkedList1.addLast(7);
        linkedList1.addLast(7);
        linkedList1.addLast(7);
        linkedList1.print();

        linkedList1.remove(7);
        linkedList1.print();

        linkedList1.removeAll(2);
        linkedList1.print();
    }

    public void clear() {
        Node cur = head;
        while (cur != null) {
            Node curNext = cur.next;
            cur.next = null;
            cur = curNext;
        }
        head = null;
    }
}
